public class TwoWayMergeSort {
    /**
     * @param array
     * @param left
     * @param mid
     * @param right
     */
    public static void merge(int[] array,int left,int mid,int right){
        int[] temp_array=new int[array.length];
        int leftStart = left;
        int rightStart = mid+1;
        int tempIndex = left;
        while (leftStart<=mid && rightStart<=right ){
            if (array[leftStart]<array[rightStart]){
                temp_array[tempIndex++]=array[leftStart++];
            }
            else{
                temp_array[tempIndex++]=array[rightStart++];
            }
        }
        while(leftStart <= mid) {
            temp_array[tempIndex++] = array[leftStart++];
        }

        while(rightStart <= right) {
            temp_array[tempIndex++] = array[rightStart++];
        }

        while(left <= right) {
            array[left] = temp_array[left++];
        }

    }

    /**
     *
     * @param array
     * @param left
     * @param right
     */
    public static void mergesort(int[] array,int left,int right){
        if (array==null){
            return;
        }
        if (left<right){
            int mid = (left+right)/2;
            mergesort(array,left,mid);
            mergesort(array,mid+1,right);
            merge(array,left,mid,right);

        }
    }

    public static void main(String[] args) {
        int[] array={3,1,8,9,6,5,2,4,7,0};
        mergesort(array,0,9);
        for (int i=0;i<array.length;i++){
            System.out.print(array[i]);
        }
    }
}
